@InProceedings{10.1007/3-540-45294-X_16,
author="Gupta, Neelima
and Chopra, Sumit
and Sen, Sandeep",
editor="Hariharan, Ramesh
and Vinay, V.
and Mukund, Madhavan",
title="Optimal, Output-Sensitive Algorithms for Constructing Upper Envelope of Line Segments in Parallel",
booktitle="FST TCS 2001: Foundations of Software Technology and Theoretical Computer Science",
year="2001",
publisher="Springer Berlin Heidelberg",
address="Berlin, Heidelberg",
pages="183--194",
abstract="In this paper we focus on the problem of designing very fast parallel algorithms for constructing the upper envelope of straight-line segments that achieve the O(n logH) work-bound for input size n and output size H. Our algorithms are designed for the arbitrary CRCW PRAM model. We first describe an O(log n {\textperiodcentered} (logH + log log n)) time deterministic algorithm for the problem, that achieves O(n logH) work bound for H = $\Omega$(log n). We present a fast randomized algorithm that runs in expected time O(logH {\textperiodcentered} log n) with high probability and does O(n logH) work. For log H = $\Omega$(log log n), we can achieve the running time of O(log H) while simultaneously keeping the work optimal. We also present a fast randomized algorithm that runs in {\~O}(log n/ log k) time with nk processors, k > log$\Omega$(1)                        n. The algorithms do not assume any input distribution and the running times hold with high probability.",
isbn="978-3-540-45294-2"
}